package 目标和;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/8 13:09
 * @description:
 */
public class Solution2 {
    public int findTargetSumWays(int[] nums, int target) {
        // dynamic programming
        // 其实就是找有多少中组合，能够刚好组成 sum / 2 的组合方式，回溯能够解决，但是会超时
        // 采用动态规划解决该问题，寻找最大组合数
        // ① dp数组及其含义：dp[i]表示容量为i时，从可选的数字中进行选择，能够刚好组成 i 的最大组合数
        // ② 动态转移公式：dp[i] = dp[i-nums[j]] + dp[i] else dp[i] = dp[i]
        // ③ dp数组初始化：dp[0] = 1代表不选任何物品，有一种方式填满背包容量为0的背包，dp[nums[0] = 1
        // ④ 遍历顺序：当前状态的确定，需要上方和左上方的状态进行确定。从右到左进行遍历防止重复选取物品!
        // ⑤ 举例推导dp数组：nums: [1, 1, 1, 1, 1], target: 3
        //             index    0   1   2   3   4
        //                      1   1   0   0   0
        //                      1   2   1   0   0
        //                      1   3   3   1   0
        //                      1   4   6   4   1
        //                      1   5   10  10  5
        // 如何确定背包容量？
        // 假设加法的总和为 x，那么减法对应的总和就是 sum - x
        //  x - (sum-x) = target  ==>  x = (target + sum) / 2

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (Math.abs(target) > sum || (target + sum) % 2 == 1) return 0;
        int bagSize = (target + sum) / 2;

        int[] dp = new int[bagSize + 1];
        // init dp
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = bagSize; j >= 0; j--) {
                if (j >= nums[i]) {
                    dp[j] = dp[j] + dp[j - nums[i]];
                }
//                else {
//                    dp[j] = dp[j];
//                }
            }
//            System.out.println(Arrays.toString(dp));
        }
        return dp[bagSize];
    }
}
